package com.giant.lsp.processPath;

import java.util.*;

public class DAGPathsFinder {

    // 图的邻接表表示
    private Map<String, List<String>> graph;

    // 构造函数，初始化图
    public DAGPathsFinder(Map<String, List<String>> graph) {
        this.graph = graph;
    }

    // 查找从源节点到所有目标节点的所有路径
    public List<List<String>> findAllPathsFromSourceToTargets(String source, Set<String> targets) {
        List<List<String>> allPaths = new ArrayList<>();
        Set<String> visited = new HashSet<>();
        List<String> currentPath = new ArrayList<>();

        dfs(source, targets, visited, currentPath, allPaths);

        return allPaths;
    }

    // 深度优先搜索（DFS）
    private void dfs(String node, Set<String> targets, Set<String> visited, List<String> currentPath, List<List<String>> allPaths) {
        currentPath.add(node);

        // 检查当前节点是否是目标节点
        if (targets.contains(node)) {
            allPaths.add(new ArrayList<>(currentPath));
        } else {
            // 遍历后继节点
            for (String neighbor : graph.getOrDefault(node, Collections.emptyList())) {
                if (!visited.contains(neighbor)) {
                    visited.add(neighbor);
                    dfs(neighbor, targets, visited, currentPath, allPaths);
                    visited.remove(neighbor); // 回溯时移除访问标记
                }
            }
        }

        currentPath.remove(currentPath.size() - 1); // 回溯
    }

    // 主函数，用于测试
    public static void main(String[] args) {
        // 示例图的邻接表表示
        Map<String, List<String>> graph = new HashMap<>();
        graph.put("A", Arrays.asList("B", "C"));
        graph.put("B", Arrays.asList("D", "E"));
        graph.put("C", Arrays.asList("F"));
        graph.put("D", Collections.emptyList());
        graph.put("E", Arrays.asList("F"));
        graph.put("F", Collections.emptyList());

        // 源节点和目标节点集合
        String source = "A";
        Set<String> targets = new HashSet<>(Arrays.asList("D", "F"));

        // 创建DAGPathsFinder实例并查找路径
        DAGPathsFinder pathsFinder = new DAGPathsFinder(graph);
        List<List<String>> allPaths = pathsFinder.findAllPathsFromSourceToTargets(source, targets);

        // 打印所有路径
        for (List<String> path : allPaths) {
            System.out.println(path);
        }
    }
}

